package com.xinheyun.demo.leetcode;

import java.util.Arrays;
import org.junit.Test;

/**
 * @description: TODO
 * @author: Sarah
 * @modified By: Sarah
 * @date: Created in 2021/8/31 14:09
 * @version:v1.0
 */
public class test279 {

    @Test
    public void numSquares() {
        int n = 13;
        int nums = (int) Math.floor(Math.sqrt(n));
        int[] dp= new int[n+1];
        for(int i =1;i<=n;i++){
            dp[i]=Integer.MAX_VALUE;
        }
        dp[0]=0;
        for(int i=1;i<=nums;i++){
            int sqrt = i*i;
            for(int j=sqrt;j<=n;j++){
                dp[j]=Math.min(dp[j-sqrt]+1,dp[j]);
            }
        }
    }

    @Test
    public void test377(){
        int nums[]={1,2,3};
        int target = 4;
       // int nums = (int) Math.floor(Math.sqrt(n));
        int[] dp= new int[target+1];
        dp[0]=1;
        for(int i = 0;i<=target;i++){
            for(int num:nums){
                if(i>=num){
                    dp[i]+=dp[i-num];
                }
            }
        }
        System.out.println(dp[target]);
    }
}
